/*
题目链接:https://leetcode.cn/problems/palindrome-partitioning-ii/description/?envType=daily-question&envId=2025-03-02
*/

//代码
#include<bits/stdc++.h>
class Solution {
public:
    //Manacher 预处理以每个位置为中心的最长回文半径
    void Manacher(string& s,vector<int>& len){
        int n = s.size();
        int c = 0,r = 0;
        for(int i=0;i<n;++i){
            len[i] = i<r ? min(len[2*c-i],r-i) : 0;
            while(i+len[i]<n && i-len[i]>=0 && s[i+len[i]]==s[i-len[i]]){
                ++len[i];
            }
            if(i+len[i]>r){
                r = i+len[i];
                c = i;
            }
        }
    }

    int minCut(string s) {
        int n = s.size();
        int m = 2*n+1;
        string t(m,'x');
        vector<int> len(m);
        for(int i=0;i<m;++i) t[i] = i&1 ? s[i/2] : '#';
        Manacher(t,len);

        //划分型dp
        vector<int> f(n+1,INT_MAX);
        f[n] = 0;
        for(int i=n-1;i>=0;--i){
            for(int j=2*i+1;j<m;++j){
                if(j&1){
                    if(len[j]/2 < j/2-i+1) continue;
                    f[i] = min(f[i],1+f[i+(j/2-i+1)*2-1]);
                }else{
                    if(len[j]/2 < (j-1)/2-i+1) continue;
                    f[i] = min(f[i],1+f[i+((j-1)/2-i+1)*2]);
                }
            }
        }
        return f[0]-1;
    }
};
int main(){
    
}